package com.klun.project.common.constans.leetcode;


/**
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 * <p>
 * 输入：nums = [2,3,1,1,4]
 * 输出：true
 * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
 */
public class Solution55 {
	// 第一次写
	public boolean canJump(int[] nums) {
		int length = nums.length;
		int[] dp = new int[length];
		if (nums[0] <= 0) {
			return false;

		}
		dp[0] = 1;
		int pointer = 0;
		for (int i = 0; i < length; i++) {
			int numsi = nums[i];
			int stepi = i + numsi;
			if (stepi > pointer) {
				pointer = stepi;
				for (int j = i + 1; j <= Math.min(stepi, length - 1); j++) {
					dp[j] = 1 & dp[j - 1];
				}
			}
		}
		return dp[length - 1] == 1;
	}

	public static void main(String[] args) {
		Solution55 solution = new Solution55();
		int[] nums = {2, 3, 1, 1, 4};
		nums = new int[]{3, 2, 1, 0, 4};
		nums = new int[]{4, 3, 2, 1, 0, 4, 8, 9, 2};
		System.out.println(solution.canJump(nums));
	}

}
